package persion.leetcode.MedianOfTwoSortedArrays;

import persion.leetcode.common.commonUtil;

import java.util.Map;

/**
 * Created by wangyifei on 19/6/9.
 */
public class Main {
    public static void main(String[] args) {
        // 这组测试集合，是有边界值的那种
       //int[] num1 = {1,2,3};
       //int[] num2 = {4,5,6};
        // 3 and 4 is median
       int median = 0 ;
       // 1 , 2 , 12 , 13 , 15 ,17
       int ar1[] = {1, 12, 15, 26, 38};
       int ar2[] = {2, 13, 17, 30, 45, 50};
       median = solotionWrapper(ar1,ar2);
       out(ar1,ar2,median);
       // 1 , 2 ,12,13,15,17
       int ar11[] = {1, 12, 15, 26, 38};
       int ar21[] = {2, 13, 17, 30, 45 };

       median = solotionWrapper(ar11,ar21);
       out(ar11,ar21,median);

       int a1[] = {1, 2, 5, 6, 8 };
       int a2[] = {13, 17, 30, 45, 50};
       median = solotionWrapper(a1,a2);
       out(a1,a2,median);

       int a10[] = {1, 2, 5, 6, 8, 9, 10 };
       int a20[] = {13, 17, 30, 45, 50};
       median = solotionWrapper(a10,a20) ;
       out(a10,a20,median);

       int a11[] = {1, 2, 5, 6, 8, 9 };
       int a21[] = {13, 17, 30, 45, 50};
       median = solotionWrapper(a11,a21) ;
       out(a11,a21,median);
       // 11
       int a12[] = {1, 2, 5, 6, 8 };
       int a22[] = {11, 13, 17, 30, 45, 50};
       median = solotionWrapper(a12,a22) ;
       out(a12,a22,median);


       int[] num1 = {1,4,6};
       int[] num2 = {2,3,5};
       median = solotionWrapper(num1,num2);
       out(num1,num2,median);

       int b1[] = {1 };
       int b2[] = {2,3,4};
       median = solotionWrapper(b1,b2);
       out(b1,b2,median);

    }

    public static void out(int[] n1 , int[] n2 , int median){
        System.out.println("median of " + commonUtil.printArray(n1) + " and "+commonUtil.printArray(n2)+" :"+ median);
    }

    public static int solotionWrapper(int[] a1 , int[] a2){
       return  a1.length <= a2.length? solotion(a1,a2):solotion(a2,a1) ;
    }


    public static int solotion(int num1[] , int num2[]){
       int i = 0 , j = 0 ;
       int len = num2.length + num1.length;
       int rs = 0 ;
       boolean loop = true ;
       int imin = 0 ;
       int imax = num1.length - 1;
       int middle = 0 ;


       if(0 == num1.length && 0 < num2.length) {
           // 奇数偶数的特殊性没有处理
           rs = num2[(num2.length-1)/2];
       }

       if(0 == num2.length && 0 < num1.length) {
           rs = num1[(num1.length-1)/2];
       }

       while(loop) {
          middle = (imin + imax)/2;

          if(middle >= num1.length - 1 && num1[middle] < num2[(len + 1)/2 - middle -1]){
             // 程序走到这里说明，middle 已经走到 A 的最右端，可推出 A[max] < B[j], 简单的将就是 A 所有的元素到了 left_set
             // if m + n is even ，the median = (max(A[max],B[j-1]) + B[j])/2 ，
             // if m + n is odd ，the median = B[j-1]
            if(len%2 == 1){
               rs = Math.max(0 > (len + 1)/2 - num1.length -1? 0 : num2[((len + 1)/2 - num1.length -1)],num1[num1.length-1]);
            }else{
               rs = (num2[(len + 1)/2 - num1.length] +
                       (0 > ((len + 1)/2 - num1.length -1)? num1[middle]:Math.min(num1[middle],num2[((len + 1)/2 - num1.length-1)] )))/2;
            }
            break;

         }

          if(middle <= 0 && ((len + 1)/2 - middle>=num2.length-1 || num1[0] > num2[((len + 1)/2 - middle>=num2.length-1?num2.length-1:(len + 1)/2 - middle)])){
             // middle 已经走到了 A 的最左端，A[0] > B[j] , 简单将，就是 A 完全在右边
             // if m + n is even , median = (B[j-1] + min(A[i],B[j]))/2
             // if m + n is odd , median = B[j-1]
            if(len%2 == 1){
                // 由于 num1.length < num2.length , 所以 num2.leng > k 的值，所以当 num1 值全部在 left_set 的时候
                // k 值一定是 0 < k < j
               rs = num2[(len+1)/2-1];
            }else{
               rs = (num2[(len + 1)/2 - 1] + ((len + 1)/2<= num1.length+1?num2[(len + 1)/2]:num1[0]))/2;
            }
              break;
          }

          if(num1[middle] > num2[(len + 1)/2 - middle -1] & num2[(len + 1)/2 - middle ] > num1[middle-1]){
              // 如果满足这个条件，那么middle 的位置就是 i 的位置。
             if(len%2 == 1) {
                 // len 为奇数的时候，由于有 i + j = m - i + n - j + 1 的限制，所以 median = max(left_set)
                 rs = Math.max(num1[middle-1],num2[(len + 1)/2 - middle -1]);
             }else{
                 //len 为奇数，median = (max(left_set)+min(right_set))/2
                 rs = ( Math.min(num1[middle],num2[(len + 1)/2 - middle]) + Math.max(num1[middle-1],num2[(len + 1)/2 - middle-1]))/2;
             }
             break;
          }
          if(num1[middle] < num2[(len + 1)/2 - middle - 1 ]){
              // 程序走到这里说明 middle 这个值小了 ，所以 imin 要变大
              imin = middle + 1;
          }

           if(num1[middle-1] > num2[(len + 1)/2 - middle ]){
               // 程序走到这里，说明 middle 这个值大了，所以 imax 要变小
               imax = middle - 1;
           }
       }
       return rs;
    }
}
